12980 - 점프와 순간 이동

정보

• 문제 보기: 12980 - 점프와 순간 이동
• 소요 시간: 44분 51초 ▶️ 4분 50초
• 풀이 언어: python java
• 체감 난이도: 2️⃣~3️⃣ ▶️ 2️⃣
• 리뷰 횟수: ✅✅

풀이 키워드

스포주의

구현 그리디

풀이 코드

Python

정보

• 메모리: 9340 KB
• 시간: 0 ms

def solution(n):
    ans = 0
    while 0 < n:
        isOdd = n & 1
        n = (n - 1 if isOdd else n // 2)
        ans += isOdd
    
    return ans

Java

정보

• 메모리: 99100 KB
• 시간: 0 ms

public class Solution {
    public int solution(int n) {
        int ans = 0;
        while (n > 0) {
            if ((n & 1) == 1) {
                ++ans;
                --n;
            }
            else n >>= 1;
        }
        
        return ans;
    }
}

풀이 해설

DP는 시간초과가 발생하여 그리디로 접근해야 하는 문제이다.

📌 역발상하기

0을 연산하여 n을 만든다고 생각하면 시작할때 무조건 1을 점프해야되고, 이 부분의 처리가 깔끔하지 않으므로

역으로 n에서 0으로 연산하는 발상이 필요하다.

📌 도착 지점의 특징 고려하기

순간이동은 $\times 2$ 연산이라서, 순간이동을 한 직후의 도착 지점은 짝수이다.

이를 명제로 적용하면 다음의 2가지 논리가 참임을 알 수 있다.

• $P \rightarrow Q$: 순간이동을 한 직후의 도착 지점은 짝수이다.
• ${\sim} Q \rightarrow {\sim} P$: 도착 지점이 홀수라면 순간이동을 한 직후가 아니다. (= 직전에 점프했다)

따라서 n -> 0으로 진행하며, 현 지점이 짝수면 역순간이동 연산을 해주고, 홀수면 역점프 연산을 해주면 된다.

역점프할땐 배터리 비용을 합산해주는것도 잊지 말자.

경고

무지성 DP 들박 좀 하지말라고

TL; DR: 빨리 풀고 싶어도 반드시 콜스택 깊이 계산할 것

$1 \le N \le 10^9$ 라고 쓰인거 봤는데 왜 무지성으로 DP 접근함?

최악의 경우 (1칸씩 이동 * 10^9) 라서 탑다운 dp는 재귀 깊이 10^9가 됨.

사고방식이 완탐 -> 아 재귀가 더 편하네 -> DP 접근 이거까지밖에 안되고 있음.

1. DP 고려 -> 범위 확인 -> OK ㄱㄱ
2. DP 고려 -> 어 범위가 좀 큰데? -> 다른 유형 고민 -> 다 안맞는 것 같은데? 로 넘어가는 것이 필요함.

2번에서 다 안맞으면 그리디로 접근하면 되고, 딱히 의심되는 유형 없으면 그리디로 바로 가는게 좋을듯.

메모

• 그리디 기초 문제같은 느낌
• 첫 풀이 체감 상 구현 난이도 1, 발상 난이도 2~3 정도였음.